#include <bits/stdc++.h>

#define MAX_SRC_P 80
#define ROOT_ID 0
#define ERR_C_MAX 10

using namespace std;

int main(int argc, char **argv) {
    FILE *offset_fp, *info_fp, *debug_fp, *bfs_result_fp;
    int *edge_offset_mem_array, *edge_mem_array;
    int *vertex_p;
    int vertex_num, edge_num, iterator_num;
    int updated;

    cout << "[INFO] Open file." << endl;
    if (argc != 4) {
        cout << "Usage : (offset_file, info_file, bfs_result_file)" << endl;
        exit (-1);
    }

    if ((offset_fp = fopen(argv[1], "r")) == NULL) {
        cout << "Failed to open file " << argv[1] << endl;
        exit (-1);
    }

    if ((info_fp = fopen(argv[2], "r")) == NULL) {
        cout << "Failed to open file " << argv[2] << endl;
        exit (-1);
    }

	if ((debug_fp = fopen("ori_bfs_debug.txt","w")) == NULL) {
        cout << "Failed to open file \"ori_bfs_debug.txt\"" << endl;
    }

    if ((bfs_result_fp = fopen(argv[3], "r")) == NULL) {
        cout << "Failed to open file " << argv[3] << endl;
        exit (-1);
    }
    cout << "[INFO] Open file complete." << endl;

    fscanf (offset_fp, "%d", &vertex_num);
    fscanf (info_fp, "%d", &edge_num);
    cout << "Vertex_num = " << vertex_num << ", Edge_num = " << edge_num << endl;

    edge_offset_mem_array   = (int *) calloc (vertex_num + 1, sizeof(int));
    edge_mem_array          = (int *) calloc (edge_num, sizeof(int));
    vertex_p                = (int *) calloc (vertex_num, sizeof(int));

    cout << "[INFO] Reading offset." << endl;
	for (int i = 0; i < (vertex_num + 1); ++ i) {
        fscanf (offset_fp, "%d", &(edge_offset_mem_array[i]));
	    if (i && (edge_offset_mem_array[i] == edge_offset_mem_array[i - 1])) {
            cout << "Invalid edge offset : vertex_id = " << i << ", off_l = " << edge_offset_mem_array[i - 1] << ", off_r = " << edge_offset_mem_array[i] << endl;
            exit (-1);
        }
	}
    cout << "[INFO] Reading offset complete." << endl;

    cout << "[INFO] Reading edge list." << endl;
	for (int i = 0; i < edge_num; ++ i) {
        fscanf (info_fp, "%d", &(edge_mem_array[i]));
    }
    cout << "[INFO] Reading edge list complete." << endl;

    fclose (offset_fp);
    fclose (info_fp);

    for (int i = 0; i < vertex_num; ++ i) vertex_p[i] = MAX_SRC_P;
    vertex_p[ROOT_ID] = 0;

    // iterator_num = atoi (argv[4]);
    iterator_num = 20;


    cout << "[INFO] Start iterate, Iterator_num = " << iterator_num << endl;
	for (int iter = 0; iter < iterator_num; ++ iter) {
        updated = 0;

        for (int i = 1; i < vertex_num; ++ i) {
            int left = edge_offset_mem_array[i];
            int right = edge_offset_mem_array[i + 1];
            int tmp = MAX_SRC_P;

            for (int j = left; j < right; ++ j) {
                if (edge_mem_array[j] >= vertex_num) {
                    tmp = min (tmp, MAX_SRC_P);
                } else {
                    tmp = min (tmp, vertex_p[edge_mem_array[j]] + 1);
                }
            }

            if (tmp < vertex_p[i]) updated = 1;
            vertex_p[i] = min(vertex_p[i], tmp);
        }

        if (!updated) {
            printf ("Max iterator number = %d.", iter);
            printf ("\n");
            break;
        }
	}
    cout << "[INFO] End iterate." << endl;

    cout << "Generate Debug file \"ori_bfs_debug.txt\"" << endl;

	for (int i = 0; i < vertex_num; ++ i) {
        fprintf(debug_fp, "%d %d\n", i, vertex_p[i]);
    }
	fclose (debug_fp);
	
    cout << "Start check." << endl;

	int bfs_result_id, bfs_result_value;
    int err_count = 0;
    int t_err_count = 0;
    int f_err_count = 0;
    int o_err_count = 0;
	for (int i = 0; i < vertex_num; ++ i) {
        fscanf (bfs_result_fp, "%d %d", &bfs_result_id, &bfs_result_value);
		if(bfs_result_id < 0 || bfs_result_id > vertex_num) {
            cout << "[ERROR] Vertex id overflow, MAX_ID = " << vertex_num << ", MIN_ID = 0, Current = " << bfs_result_id << endl;
			exit(-1);
		}
		if (vertex_p[bfs_result_id] != bfs_result_value) {
            int t_or_f = vertex_p[bfs_result_id] < bfs_result_value ? 0 : 1;
            if (t_or_f && t_err_count < ERR_C_MAX) {
                cout << "[T_ERROR] ID = " << bfs_result_id << ", ACC_V = " << bfs_result_value << ", R_V = " << vertex_p[bfs_result_id] << endl;
            } else if (!t_or_f && f_err_count < ERR_C_MAX) {
                cout << "[F_ERROR] ID = " << bfs_result_id << ", ACC_V = " << bfs_result_value << ", R_V = " << vertex_p[bfs_result_id] << endl;
            }
            f_err_count = t_or_f ? f_err_count : f_err_count + 1;
            t_err_count = t_or_f ? t_err_count + 1 : t_err_count;
            err_count ++;
            o_err_count = vertex_p[bfs_result_id] == MAX_SRC_P ? o_err_count + 1 : o_err_count;
		}
	}
    cout << "[INFO] ERR = " << err_count << ", False_ERR = " << f_err_count << ", True_ERR = " << t_err_count << ", Other_ERR = " << o_err_count << endl;
    if (err_count == 0) {
        cout << "[INFO] Check pass." << endl;
    } else {
        cout << "[INFO] Check failed." << endl;
    }
    cout << "End check." << endl;
}
